package com.lintcode.solution;

import java.util.Arrays;
import java.util.Collections;

public class Solution_38 {
    public static void main(String[] args) {
        Solution_38 solution = new Solution_38();
        int[][] a =
                { { 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80 }, { 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81 }, { 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82 }, { 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83 }, { 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84 }, { 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85 } };
        //        int[][] a = { { 1, 3, 5, 7 }, { 2, 4, 7, 8 }, { 3, 5, 9, 10 } };
        System.out.println(solution.searchMatrix(a, 3));
    }
    
    public int searchMatrix(int[][] matrix, int target) {
        int result = 0;
        for (int i = 0; i < matrix.length; i++) {
            int length = matrix[ i ].length;
            if (target >= matrix[ i ][ 0 ] && target <= matrix[ i ][ length - 1 ]) {
                for (int j = 0; j < matrix[ i ].length; j++) {
                    if (matrix[ i ][ j ] == target) {
                        result++;
                        break;
                    }
                }
            }
        }
        
        return result;
    }
}
